1. Field of the Invention
This invention is in the field of methods and apparatus for calculating the residue of a binary number with respect to a predetermined check base. The residues of such numbers can be used in the binary and arithmetic unit of a digital data processing system to check the accuracy of arithmetic operations performed on two operands, each of which operations produces a result.
2. Description of the Prior Art
To assure the accuracy of arithmetic operations on binary numbers in digital data processors, there is a need to validate such operations. Various ways of doing this have been developed, such as by parallel execution of the same operation on the same operands, or the use of parity checks at each stage of an operation. Another way to validate the accuracy of arithmetic operations such as addition, subtraction, multiplication, and division of binary numbers is to validate each operation using residue theory mathematics in which the residue (r) of a number, or operand, "X" is the remainder resulting from the division of "X" by the check base "m" or EQU X=km+r
where k is an integer constant such that r is equal to or greater than 0 and less than m. A common representation of this definition is EQU r=.vertline.X.vertline.m.
Any arithmetic operation .phi. performed on two operands A and B which produces a resultant R can be represented as EQU R=.phi.(A,B).
The basic residue theory check equation is EQU .vertline.R.vertline.m=.phi.(.vertline.A.vertline.m, .vertline.B.vertline.m).
Thus, the residue of the resultant R is equal to the operation .phi. performed on the residues of the operands A and B. The operation .phi. performed on the residues is defined as being executed in modulo m arithmetic. The significance of the foregoing is that, if an arithmetic operation is performed on two operands, then the residue of the result of that operation will equal the same operation performed on the residues of the two operands, it being a requirement that all residues are determined with respect to the same check base m. Residue checking has the advantage that it will detect all single bit errors in the resultant R.
To use residue checking to verify the accuracy of arithmetic operations requires digital apparatus for calculating the residues of the operands and the residue of the resultant of each such operation. There also is a requirement for arithmetic logic to perform the same operation on the residues of the operands as is performed on the operands themselves. Finally, there is a need for comparator logic to compare the residues of the resultants calculated both ways to ascertain that they are the same.
Since division of one binary number by another normally requires more time and logic to accomplish than any other binary arithmetic operation, it is necessary to implement the mathematical operation that will effectively divide an operand or resultant by the check base without performing the actual division. It is known that the residue r of X, an n bit binary number, with respect to a check base m=2.sup.b -1, can be calculated by partitioning X into segments of b bits per segment and by adding the segments using 1's complement addition until the segments are reduced to a single segment of b bits with the single segment being the residue r of X.
The comparative slowness of 1's complement adders such as that disclosed in U.S. Pat. No. 4,298,952, which issued on Nov. 3, 1981, has heretofore significantly reduced the usefulness of residue checking to verify the accuracy of arithmetic operations on large binary number operands in high-speed digital data processing systems. There is, therefore, a need for a significantly faster method and apparatus for calculating the residues of binary operands.